寻找第K大

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param a int整型一维数组 
# @param n int整型 
# @param K int整型 
# @return int整型
#
class Solution:
    def findKth(self , a: List[int], n: int, K: int) -> int:
        # write code here
        import heapq
        res = ""
        if n >= K:
            qp = []
            for i in range(K):
                heapq.heappush(qp, a[i])
            for i in range(K, n):
                if a[i] > qp[0]:
                    heapq.heapreplace(qp, a[i])
            res = qp[0]
        return res

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param a int整型一维数组 
# @param n int整型 
# @param K int整型 
# @return int整型
#
class Solution:
    def findKth(self , a: List[int], n: int, k: int) -> int:
        # write code here       
        res=[]
        if n< k&nbs***bsp;n<=0:
            return res
        else:
            import heapq
            q=[]
            for i in range(k):#构建小顶堆
                heapq.heappush(q,a[i])
            for i in range(k,n):
                if q[0] < a[i]:#最大的k个里面的最小的，
                    heapq.heapreplace(q,a[i])
            res=heapq.heappop(q)#堆顶元素就是第k大
            return res
    

class Solution:
    def findKth(self , a: List[int], n: int, K: int) -> int:
        # write code here
        import heapq
        return heapq.nlargest(K, a)[-1]

class Solution:
    def findKth(self , a: List[int], n: int, K: int) -> int:
        # write code here
        if not a: return None
        if K > len(a): return None
        a.sort()
        a.reverse()
        return a[K-1]

请问各位大佬，我的“快速排序”怎样修改才能不超时？

class Solution:
def findKth(self , a: List[int], n: int, K: int) -> int:
# write code here

    if len(a) == 0:
        return None

    def partition(a,l,r):
        p = l
        for i in range(l,r):
            if a[i] > a[r]:
                a[i],a[p] = a[p],a[i]
                p += 1
        a[r],a[p] = a[p],a[r]  
        return p
    def quick_sort(a,left,right):
        if left < right:
            pos = partition(a,left,right)
            quick_sort(a,left, pos-1)
            quick_sort(a,pos+1, right)       

    quick_sort(a, 0, len(a)-1)
    return a[K-1]

class Solution:
    def findKth(self , a: List[int], n: int, K: int) -> int:
        # write code here
        a=sorted(a,reverse=True)
#         print(a)
        return a[K-1]

不讲理

利用快排思想 + 随机初始化基数，不初始化用例过不了

import random
class Solution:
    def partition(self, a, low, high):
        m =random.randrange(low, high+1)
        a[low], a[m] = a[m], a[low]
        temp = a[low]
        while low < high:
            while low < high and a[high] < temp:
                high -= 1
            a[low] = a[high]
            while low < high and a[low] >= temp:
                low += 1
            a[high] = a[low]
        a[low] = temp
        return low
    def quick_sort(self, a, low, high, k):
        p = self.partition(a, low, high)
        if p-low+1 == k:
            return a[p]
        elif p-low+1 > k:
            return self.quick_sort(a, low, p-1, k)
        else:
            return self.quick_sort(a, p+1, high, k-(p-low+1))

    def findKth(self , a: List[int], n: int, K: int) -> int:
        return self.quick_sort(a, 0, n-1, K)

# 方法一，采用python内置的sort函数，虽然很讨巧，但是能通过，而且效率也还行
class Solution:
    def findKth(self , a: List[int], n: int, K: int) -> int:
        # write code here
        # 对a进行快速排序
        a.sort()
        #print(a)
        #print(a[-K])
        return a[-K]

# 方法二：本质按照题目的思想，时间复杂度O(N),空间复杂度O(1),采用堆排序的思路
# 自己建堆的效率果然还是比不上系统内置的sort(),虽然也能够勉强AC
# 但是如果是自己用partttion+二分法写快排是一定会超时的，也看到题解有将pivot设置成随机数通过的
# 以下为自建堆排序的代码
class Solution:
    def findKth(self , a: List[int], n: int, K: int) -> int:
        # write code here
        def KeepHeap(arr, parent, high):
            # 假设只有根节点需要调整，两棵子树都是堆
            child = parent *2 +1 #child 指向i的左子树
            temp = arr[parent]
            while child <high:
                # 获取根以及左右子节点的最大值
                # 先比较左右子节点的值
                # 右子树比较大,则指向右子树
                if child+1< high and arr[child] < arr[child+1]:
                    child +=1
                # 如果父节点的值已经大于孩子节点的值，说明在正确位置上
                # 直接结束
                if temp >=arr[child]:
                    break
                # 如果左右字子节点的值大于父节点，将最大值赋给根节点
                arr[parent] = arr[child]
                parent = child
                # 子节点发生变化，从它的左子节点开始
                child = 2 * parent + 1
            # 将temp值放到最终的位置
            arr[parent]=temp   
        def Heap_Sort(arr):
            # 1、建堆
            # 根据升序降序需求选择大顶堆和小顶堆，这采用的大顶堆，最后是升序的序列
            # 先找到最后一个不是叶子节点的根节点
            # 再向上循环根节点，从小到大
            n = len(arr)
            for i in range(n//2-1, -1, -1):
                KeepHeap(arr,i,n)

            # 2、挨个出数，按升序排列
            # 将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端，此时数组末端存储了当前区间最大的元素
            for i in range(n-1, -1, -1):
                arr[0], arr[i] = arr[i], arr[0]
                KeepHeap(arr, 0, i)
        Heap_Sort(a)
        #print(a)
        return a[-K]

class Solution:
    def findKth(self , a: List[int], n: int, K: int) -> int:
        # write code here
        return sorted(a,reverse=True)[K-1]

    def findKth(self , a: List[int], n: int, K: int) -> int:
        # write code here
        #         a.sort()
        def quickSort(arr):
            if len(arr) < 2: return arr
#             pivot = arr[0]
            pivot = arr[len(arr) // 2]  # 使用向下取整能够通过所有测试用例.
            left = [x for x in arr if x < pivot]
            middle = [x for x in arr if x == pivot]
            right = [x for x in arr if x > pivot]
            
            return quickSort(left) + middle + quickSort(right)
        a = quickSort(a)
        return a[-K]

class Solution:
    def findKth(self , a: List[int], n: int, K: int) -> int:
        for i in range(n - 1):
            for j in range(i + 1, n):
                if a[i] < a[j]:
                    a[i], a[j] = a[j], a[i]
        return(a[K - 1])